package basic.study.algorithms.solution.recall;

import java.util.Arrays;
import java.util.Stack;

/**
 * @author Kevin
 * @date 2020/4/6 18:08
 * 题目
 * 1□２□３□４□５□６□７□８□９＝１１０
 * 要求在中间的８个空中填写＋，－，或不填。构成的表达式判断是不是正确，正确则输出。。。。
 * （如果空格的中没有填写符号，则这几个数组成一个新的Ｎ位数，比如１□２，可以是１＋２，也可以是１２）
 * https://blog.csdn.net/XZ2585458279/article/details/88740785
 */
public class Plus {
    int n;//层次
    int result = 0;//统计结果
    int[] bestx;//保存操作符
    int[] a;//运算数
    Stack<Integer> data;//数据栈
    Stack<Integer> oper;//运算符栈

    public Plus() {
        //int n;//层次
        //int result = 0;//统计结果
        //int bestx[9] = {-1};//保存操作符
        bestx = new int[9];
        Arrays.fill(bestx, -1);
        //int a[10] = {1,2,3,4,5,6,7,8,9};//运算数
        a = new int[]{1,2,3,4,5,6,7,8,9};
        //stack<int> data;//数据栈
        data = new Stack<>();
        //stack<int> oper;//运算符栈
        oper = new Stack<>();

    }

    public void calc(int n) {
        if (n == 9) {//最后一层运算符计算
            while (!oper.empty()) {
                int b1 = data.pop();//第二个整数
                int a1 = data.pop();//第一个整数
                int op = oper.pop();//当前运算符
                if (op == 0) {
                    data.push(a1 + b1);
                } else if(op == 1){
                    data.push(a1 - b1);
                }
            }
            int result = data.peek();//最终结果
            if (result == 110) {//输出
                System.out.print(1);
                for (int i = 0; i <= 8; i++) {
                    if (bestx[i] == 0) System.out.print("+");
                    else if (bestx[i] == 1) System.out.print("-");
                    System.out.print(a[i]);
                }
                System.out.print("=110");
                System.out.println();
            }
            return;
        }

        for (int i = 0; i < 3; i++) {
            Stack<Integer> oper_temp = (Stack<Integer>)oper.clone();//原来是oper，我改的
            Stack<Integer> data_temp = (Stack<Integer>)data.clone();//原来是data
            if (i == 0) {
                bestx[n] = 0;
                if (!oper.empty()) {
                    int op = oper.peek();
                    if (op == 1) {//之前运算符是减
                        oper.pop();
                        oper.push(0);//将减号变成加号
                        int tp = data.pop();
                        data.push(-tp);
                    }
                }
                oper.push(bestx[n]);
                data.push(a[n]);
            } else if(i == 1) {
                bestx[n] = 1;
                if (!oper.empty()) {
                    int op = oper.peek();
                    if (op == 1) {//之前运算是减
                        oper.pop();
                        oper.push(0);//把减号变成加号
                        int tp = data.pop();
                        data.push(-tp);
                    }
                }
                oper.push(bestx[n]);
                data.push(a[n]);
            } else {
                bestx[n] = 2;
                int temp = data.pop();
                temp = temp * 10 + a[n];
                data.push(temp);
            }

            calc(n+1);
            oper = oper_temp;
            data = data_temp;
        }

    }

    public static void main(String[] args) {
        Plus p = new Plus();
        p.data.push(1);
        p.calc(1);
    }
}
